package com.xsherl.leetcode.solution;

import com.xsherl.leetcode.utils.PrintUtils;

import java.util.ArrayList;
import java.util.List;

public class PermutationSequence {

    /**
     * 由于 n 个元素有 n! 种排列，当 k > (n - 1)!时，
     * 所以当需要第一次变动第一位数字时 k == (n - 1)! + 1;
     * 因此第一位数字s[0] = (k - 1) / (n - 1)!, k = (k - 1) % (n - 1)! + 1
     *
     * 我们可以把所以元素按顺序放到链表中，当链表中元素被使用时，删除它
     *  比如 123 这个组合：
     *     下标： 0 1 2
     *   组合数:  6 2 1
     *     链表： 1 2 3
     *
     *  所以当 k = 3 时，
     *      s[0] = list[(3 - 1) / 2] = list[1] = 2; k = (3 - 1) % 2 = 0; list = [1, 3]
     *      s[1] = list[0] = 1; list = [3]
     *      s[2] = list[0] = 3;
     *  所以最终结果为 213
     *
     * 当 k = 4 时，
     *      s[0] = list[4 / (2 + 1)] = list[1] = 2; k = 4 % (2 + 1) = 1; list = [1, 3]
     *      s[1] = list[1] = 3; list = [1]
     *      s[2] = list[0] = 1;
     *
     *
     * @param n 1 <= n <= 9
     * @param k 1 <= k <= n!
     */
    public String getPermutation(int n, int k) {
        List<Integer> ints = new ArrayList<>(n);
        int t = 1;
        for (int i = 1; i <= n; ++i){
            ints.add(i);
            t *= i;
        }
        t /= n;
        k--;
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i < n; ++i) {
            int index = k / t;
            PrintUtils.println(k, t, index, ints);
            sb.append(ints.get(index));
            ints.remove(index);
            k = k % t;
            t /= (n - i);
        }
        sb.append(ints.get(0));
        return sb.toString();
    }

    public static void main(String[] args) {
        int n = 4;
        int k = 9;
        String permutation = new PermutationSequence().getPermutation(n, k);
        System.out.println(permutation);
    }
}
